package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_368 {

    public static void main(String[] args) {
        Solution_368 model = new Solution_368();
        System.out.println(model.largestDivisibleSubset(new int[]{3, 17}));
        System.out.println(model.largestDivisibleSubset(new int[]{1}));
        System.out.println(model.largestDivisibleSubset(new int[]{1,2,3}));
        System.out.println(model.largestDivisibleSubset(new int[]{1,2,4,8}));
    }

    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int[][] counts = new int[nums.length][2];
        counts[0] = new int[]{1, -1};
        int maxIndex = 0;
        for (int i = 1; i < nums.length; i++) {
            counts[i] = new int[]{1, -1};
            int preIndex = i;

            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    if (counts[j][0] + 1 > counts[preIndex][0]) {
                        preIndex = j;
                    }
                }
            }
            if (preIndex != i) {
                counts[i][0] = counts[preIndex][0] + 1;
                counts[i][1] = preIndex;
            }

            if (counts[i][0] > counts[maxIndex][0]) {
                maxIndex = i;
            }
        }
        List<Integer> list = new ArrayList<>();
        do {
            list.add(0, nums[maxIndex]);
            maxIndex = counts[maxIndex][1];
        } while (maxIndex >= 0);
        return list;
    }
}
